package demo.practice.tree.segment;

public class SegmentTree {
    int[] tree;
    int[] data;

    SegmentTree(int[] data) {

        if (data == null || data.length == 0) {
            throw new RuntimeException("初始化数组不为空(can't build a no element tree)");
        }

        this.data = data;
        tree = new int[data.length * 4];
        build(0, 0, data.length - 1);
    }

    //        【1、2、3、4、5、6、7】   treeindex=0
    //           /           \
    //    【1、2、3]        【4、5、6、7】          treeindex=1和 treeindex=2
    //     /    \            /    \
    // 【1】 【2、3】      【4、5】  【6、7】       treeindex分别等于  3、4、5、6
    //       /  \        /   \    /  \          //根据完全二叉树的性质 父子关系为 父为n，则有左子为 2*n+1 右子为2*n+2
    //     【2】【3】    【4】【5】【6】【7】


    /**
     * @param treeindex tree对应节点的索引
     * @param l         构建时，arr的左边界
     * @param r         构建时，arr的右边界
     */
    private void build(int treeindex, int l, int r) {
        if (l == r) {
            tree[treeindex] = data[l];
            return;
        }

        int mid = l + (r - l) / 2;
        //左边
        build(treeindex * 2 + 1, l, mid);
        //右边
        build(treeindex * 2 + 2, mid + 1, r);
        //左边加上右边得到父亲节点
        tree[treeindex] = tree[treeindex * 2 + 1] + tree[treeindex * 2 + 2];
    }

    /**
     * 查询接口
     */
    public int query(int l, int r) {
        //查询数组区间 l~r的和
        if (l > r) {
            throw new RuntimeException("输入的区间错误(input l must litte than r)");
        }
        return query(0, 0, data.length - 1, l, r);
    }

    /**
     * 查询辅助函数，归并思想
     *
     * @param treeindex tree对应节点的索引
     * @param tl        tree当前值对应  arr范围的左边界
     * @param tr        tree当前值对应  arr范围的右边界
     *                  综合起来相当于 tree[treeindex] = arr[tl~tr]的和
     * @param l         查询范围的左边界
     * @param r         查询范围的右边界
     */
    private int query(int treeindex, int tl, int tr, int l, int r) {
        //刚好就查到了
        if (tl == l && tr == r) {
            return tree[treeindex];
        }

        //直接越界了，查不到
        if (l > tr || r < tl) {
            return 0;
        }

        int mid = tl + (tr - tl) / 2;
        //l~ mid为左边区间、 (mid + 1)~r 为右边区间
        if (r <= mid) {
            //直接去左边区间找
            return query(treeindex * 2 + 1, tl, mid, l, r);
        }
        if (l > mid) {
            //直接去右边区间找
            return query(treeindex * 2 + 2, mid + 1, tr, l, r);
        }
        return query(treeindex * 2 + 1, tl, mid, l, mid) +
                query(treeindex * 2 + 2, mid + 1, tr, mid + 1, r);
    }

    /**
     * 更新接口
     */
    public void update(int index, int value) {
        if (index > data.length - 1 || index < 0) {
            throw new RuntimeException("输入的区间错误(input l must litte than r)");
        }
        data[index] = value;
        update(0, 0, data.length - 1, index, value);
    }

    /**
     * 更新辅助函数，归并思想
     *
     * @param treeindex tree对应节点的索引
     * @param tl        tree当前值对应  arr范围的左边界
     * @param tr        tree当前值对应  arr范围的右边界
     *                  综合起来相当于 tree[treeindex] = arr[tl~tr]的和
     */
    private void update(int treeindex, int tl, int tr, int index, int value) {

        if (tl == tr && index == tl) {
            tree[treeindex] = value;
            return;
        }

        int mid = tl + (tr - tl) / 2;
        //l~ mid为左边区间、 (mid + 1)~r 为右边区间
        if (index <= mid) {
            update(treeindex * 2 + 1, tl, mid, index, value);
        }
        if (index > mid) {
            update(treeindex * 2 + 2, mid + 1, tr, index, value);
        }
        //需要在此更新一下父节点
        tree[treeindex] = tree[treeindex * 2 + 1] + tree[treeindex * 2 + 2];
    }
}
